Decrease elements to make array zigzag

Time: O(N); Space: O(1); medium

Given an array nums of integers, a move consists of choosing any element and decreasing it by 1.

An array A is a zigzag array if either: * Every even-indexed element is greater than adjacent elements, ie. A[0] > A[1] < A[2] > A[3] < A[4] > … * OR, every odd-indexed element is greater than adjacent elements, ie. A[0] < A[1] > A[2] < A[3] > A[4] < …

Return the minimum number of moves to transform the given array nums into a zigzag array.

Example 1:

Input: nums = [1,2,3]

Output: 2

Explanation:

  • We can decrease 2 to 0 or 3 to 1.

Example 2:

Input: nums = [9,6,1,6,2]

Output: 4

Notes:

  • 1 <= len(nums) <= 1000

  • 1 <= nums[i] <= 1000

[1]:

class Solution1(object):
    def movesToMakeZigzag(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = [0, 0]
        for i in range(len(nums)):
            left = nums[i-1] if i-1 >= 0 else float("inf")
            right = nums[i+1] if i+1 < len(nums) else float("inf")
            result[i % 2] += max(nums[i] - min(left, right) + 1, 0)
        return min(result)

[2]:

s = Solution1()
nums = [1,2,3]
assert s.movesToMakeZigzag(nums) == 2
nums = [9,6,1,6,2]
assert s.movesToMakeZigzag(nums) == 4